package com.njupt.Tree;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/12/2 15:45
 * @Description: 106. 从中序与后序遍历序列构造二叉树
 * @Version: 1.0
 */


public class BuildTreePostIn {

    private int currentIndex;

    public TreeNode buildTree(int[] inorder, int[] postorder) {


        int left = 0;
        int right = inorder.length - 1;
        this.currentIndex = postorder.length - 1;
        if (inorder.length == 1 && inorder[0] == -1) {
            return new TreeNode(-1);
        }

        boolean[] flag = new boolean[inorder.length];
        return build(left, right, this.currentIndex, inorder, postorder, flag);


    }

    private TreeNode build(int left, int right, int currentIndex, int[] inorder, int[] postorder, boolean[] flag) {

        if (left > right || currentIndex < 0) return null;

        int val = postorder[currentIndex];
        int mid = Arrays.stream(inorder).mapToObj(v -> Integer.valueOf(v)).collect(Collectors.toList()).indexOf(val);
        flag[mid] = true;
        TreeNode root = new TreeNode(val);
        int rightIndex = index0fRight(flag, mid);
        this.currentIndex--;
        root.right = build(mid + 1, rightIndex, this.currentIndex, inorder, postorder, flag);
        int leftIndex = indexOfLeft(flag, mid);
        root.left = build(leftIndex, mid - 1, this.currentIndex, inorder, postorder, flag);

        return root;
    }

    private int indexOfLeft(boolean[] flag, int mid) {
        int i = mid;
        for (i = mid - 1; i >= 0; i--) {
            if (flag[i] == true) {
                return i + 1;
            }
        }
        return i + 1;
    }

    private int index0fRight(boolean[] flag, int mid) {
        int i = mid;
        for (i = mid + 1; i < flag.length; i++) {
            if (flag[i] == true) {
                return i - 1;
            }
        }

        return i - 1;
    }

    public static void main(String[] args) {
        int[] inorder = {9, 3, 15, 20, 7};
        int[] postorder = {9, 15, 7, 20, 3};

//        int i = Arrays.stream(inorder).mapToObj(e -> Integer.valueOf(e)).collect(Collectors.toList()).indexOf(3);


//        //报错的原因Arrays.stream(inorder)返回的是IntStream是一个原始流，只能处理int类型的数据
//        //map函数是专门用户处理对象类型的流
//        //因此不能直接对 IntStream 使用 map() 来进行类型转换
//        Arrays.stream(inorder)
//                .map(e -> Integer.valueOf(e))
//                .collect(Collectors.toList());

        BuildTreePostIn test = new BuildTreePostIn();
        TreeNode root = test.buildTree(inorder, postorder);
        System.out.println();
    }
}
